package edu.xidian.sei.mlcs;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

import edu.xidian.sei.mlcs.util.Logger;
import edu.xidian.sei.mlcs.util.Queues;
import edu.xidian.sei.mlcs.util.Stopwatch;

/**
 * 通过入度标记每个节点的单项图，所有节点的层级是通过拓扑排序进行设置
 * 
 * @author chaostone
 */
public class Graph {
  private Mlcs mlcs;
  // Location -> Node
  private Map<Location, Node> location2Nodes = new java.util.HashMap<Location, Node>();
  private Set<Location> keyLocs; // 关键点
  private Set<Location> heads = new java.util.HashSet<Location>(4);// 已经访问过起点之后的那些路

  private int maxLevel = -1;// 匹配的字符串最长值
  private BigDecimal matchedCount = new BigDecimal(0); // 匹配的结果数量

  private Node start = null; // 起点
  private Node end = null; // 终点
  private Logger logger = Logger.getLogger(Graph.class);

  public Graph(Mlcs mlcs) {
    this.mlcs = mlcs;
    start = newNode(mlcs.start);
    end = newNode(mlcs.end);
  }

  public Node get(Location loc) {
    return location2Nodes.get(loc);
  }

  /**
   * 访问图中的虚拟起点之后的某一路,这一路的起点不计入度，当最后拓扑排序时再行增加入度。
   * 
   * @return true 如果这一路没有访问过
   * @see setLevel
   */
  public boolean accessHead(Location start, Location to) {
    if (heads.contains(to)) {
      return false;
    } else {
      heads.add(to);
      Node n = location2Nodes.get(to);
      if (null == n) {
        n = newNode(to);
        n.indegree = 0;
        return true;
      } else {
        return false;
      }
    }
  }

  public int size() {
    return location2Nodes.size();
  }

  /**
   * 向图中添加一个边
   * 
   * @return true 如果to没有访问过，可以继续访问
   */
  public boolean addEdge(Location start, Location to) {
    Node n = location2Nodes.get(to);
    if (null == n) {
      newNode(to);
      return true;
    } else {
      n.inc();
      return false;
    }
  }

  public void addLocation(Location loc) {
    if (!location2Nodes.containsKey(loc)) {
      Node n = newNode(loc);
      n.indegree = 0;
    }
  }

  public boolean exists(Location loc) {
    return location2Nodes.containsKey(loc);
  }

  /**
   * 针对每个节点进行拓扑排序的任务
   */
  @SuppressWarnings("serial")
  static class LevelCrawler extends RecursiveTask<List<Location>> {
    Graph graph;
    ArrayList<Location> locations;
    int from, to, level;

    public LevelCrawler(Graph graph, int level, ArrayList<Location> locations, int from, int to) {
      super();
      this.graph = graph;
      this.level = level;
      this.locations = locations;
      this.from = from;
      this.to = to;
    }

    public List<Location> compute() {

      List<Location> nexts = new LinkedList<Location>();
      for (int i = from; i < to; i++) {
        Location loc = locations.get(i);
        Node fromNode = graph.get(loc);
        List<Location> successors = graph.mlcs.nextLocations(loc);
        if (successors.isEmpty()) {
          graph.end.addEndPredecessor(fromNode, level + 1);
        } else {
          for (Location to : successors) {
            Node toNode = graph.get(to);
            // 如果是空的情况，是上次图缩水导致的
            if (null != toNode && toNode.addPredecessor(fromNode, level + 1)) nexts.add(to);
          }
        }
      }
      return nexts;
    }
  }

  /**
   * 根据节点的入度，1）进行设置层级，2）设置后继节点的前趋
   */
  private void setLevel() {
    maxLevel = -1;
    linkKeyNodes();

    long startTime = System.nanoTime();
    ForkJoinPool pool = null;
    if (mlcs.maxThread > 0) pool = new ForkJoinPool(mlcs.maxThread);
    else pool = new ForkJoinPool();

    ArrayList<Location> levelQueue = new ArrayList<Location>();
    levelQueue.add(mlcs.start);

    int parallelism = pool.getParallelism();
    while (!levelQueue.isEmpty()) {
      maxLevel += 1;
      List<int[]> segs = Queues.split(levelQueue.size(), parallelism);
      LinkedList<ForkJoinTask<List<Location>>> tasks = new java.util.LinkedList<ForkJoinTask<List<Location>>>();
      for (int[] seg : segs) {
        tasks.add(pool.submit(new LevelCrawler(this, maxLevel, levelQueue, seg[0], seg[1])));
      }
      levelQueue = new ArrayList<Location>();
      for (ForkJoinTask<List<Location>> task : tasks) {
        levelQueue.addAll(task.join());
      }
    }
    pool.shutdown();
    if (logger.isDebugEnabled()) {
      logger.debug("set level using " + Stopwatch.format(System.nanoTime() - startTime));
    }
  }

  /**
   * 找到关键结点(不包括起点和终点）
   */
  private void findKeyLocs() {
    setLevel();

    long startTime = System.nanoTime();
    keyLocs = new java.util.HashSet<Location>();
    LinkedList<Location> queue = new java.util.LinkedList<Location>();
    int tlevel = 0;
    // 从虚拟终点到该节点的可选路径数，初始终点为1
    Map<Location, BigDecimal> routeCounts = new java.util.HashMap<Location, BigDecimal>();
    routeCounts.put(end.loc, new BigDecimal(1));

    Location queueEnd = mlcs.end;
    Location nextQuenEnd = null;
    queue.addLast(mlcs.end);

    while (!queue.isEmpty()) {
      Location loc = queue.removeFirst();
      Node node = location2Nodes.get(loc);
      for (Node p : node.predecessors) {
        Location ploc = p.loc;
        if (p.level + tlevel == maxLevel) {
          if (keyLocs.contains(ploc)) {
            routeCounts.put(ploc, routeCounts.get(ploc).add(routeCounts.get(loc)));
          } else {
            keyLocs.add(ploc);
            nextQuenEnd = ploc;
            routeCounts.put(ploc, routeCounts.get(loc));
            queue.addLast(nextQuenEnd);
          }
        }
      }
      if (loc == queueEnd) {
        queueEnd = nextQuenEnd;
        tlevel += 1;
      }
    }
    keyLocs.remove(start.loc);
    keyLocs.remove(end.loc);
    matchedCount = routeCounts.get(start.loc);
    if (logger.isDebugEnabled()) {
      logger.debug("find key location using " + Stopwatch.format(System.nanoTime() - startTime));
    }
  }

  /**
   * 统计结果
   */
  public Mlcs.Result stat() {
    findKeyLocs();
    return new Mlcs.Result(matchedCount, maxLevel);
  }

  /**
   * 求解关键路径，删除冗余节点
   */
  public void shrink() {
    long startTime = System.nanoTime();
    findKeyLocs();
    int size = location2Nodes.size();
    buildNewMap();
    logger.info("graph shinked, " + (size - location2Nodes.size()) + " removed," + location2Nodes.size()
        + " reminded. using " + Stopwatch.format(System.nanoTime() - startTime));
  }

  /**
   * 根据关键点构建一个新图
   */
  private void buildNewMap() {
    Map<Location, Node> newLocation2Nodes = new java.util.HashMap<Location, Node>();
    // 将起点和终点加入map
    newLocation2Nodes.put(mlcs.start, start.reset());
    newLocation2Nodes.put(mlcs.end, end.reset());

    for (Location loc : keyLocs) {
      Node node = location2Nodes.get(loc).reset();
      newLocation2Nodes.put(loc, node);
    }

    this.location2Nodes = newLocation2Nodes;
  }

  private void linkKeyNodes() {
    long startTime = System.nanoTime();
    start.indegree = 0;
    if (!heads.isEmpty() || null != keyLocs && !keyLocs.contains(mlcs.start)) {
      for (Location head : mlcs.nextLocations(mlcs.start)) {
        if (location2Nodes.containsKey(head)) {
          heads.add(head);
          location2Nodes.get(head).inc();
        }
      }
    }
    if (null == keyLocs) return;
    for (Location loc : keyLocs) {
      for (Location next : mlcs.nextLocations(loc)) {
        Node node = location2Nodes.get(next);
        if (null != node) node.inc();
      }
    }
    if (logger.isDebugEnabled()) {
      logger.debug("merge map(" + keyLocs.size() + " locations) using "
          + Stopwatch.format(System.nanoTime() - startTime));
    }
  }

  @SuppressWarnings("unused")
  private void printState() {
    List<Location> locations = new ArrayList<Location>(location2Nodes.keySet());
    Collections.sort(locations, mlcs.sorter);
    for (Location loc : locations) {
      Node node = location2Nodes.get(loc);
      System.out.println(loc + " indgre:" + node.indegree);
    }
  }

  /**
   * 打印路径结果
   */
  public void printPathResult() {
    List<List<Location>> paths = findKeyPaths();
    for (List<Location> path : paths) {
      for (Location l : path)
        System.out.print(mlcs.charAt(l));
      System.out.println();
    }
  }

  public List<List<Location>> findKeyPaths() {
    LinkedList<List<Location>> results = new LinkedList<List<Location>>();
    collectPath(end, new LinkedList<Location>(), results);
    return results;
  }

  private void collectPath(Node n, List<Location> suffix, LinkedList<List<Location>> result) {
    int maxLevel = n.level - 1;
    List<Node> predecessors = new ArrayList<Node>();
    for (Node p : n.predecessors) {
      if (p.level == maxLevel) predecessors.add(p);
    }
    for (Node e : predecessors) {
      List<Location> newPaths = new ArrayList<Location>();
      newPaths.add(e.loc);
      newPaths.addAll(suffix);
      if (!e.predecessors.isEmpty()) {
        if (e.predecessors.contains(start)) {
          result.add(newPaths);
        } else {
          collectPath(e, newPaths, result);
        }
      }
    }
  }

  private Node newNode(Location to) {
    Node n = new Node(to);
    location2Nodes.put(to, n);
    return n;
  }

  // 不要实现equals和hashcode,使用原始的。否则这样会降低在前趋后继的扩充时间开销
  static class Node {
    public Location loc;
    public short indegree;
    public short level;
    public List<Node> predecessors = new ArrayList<Node>();

    public Node(Location loc) {
      this.indegree = 1;
      this.loc = loc;
    }

    public Node reset() {
      this.predecessors = new ArrayList<Node>();
      this.indegree = 0;
      this.level = 0;
      return this;
    }

    public void inc() {
      indegree = (short) (indegree + 1);
    }

    /**
     * 向虚拟终点添加前趋
     */
    public synchronized void addEndPredecessor(Node predecessor, int newLevel) {
      if (this.level < newLevel) {
        this.level = (short) newLevel;
        predecessors = new ArrayList<Node>();
      }
      predecessors.add(predecessor);
    }

    /**
     * 添加前趋
     */
    public synchronized boolean addPredecessor(Node predecessor, int newLevel) {
      if (this.level < newLevel) {
        this.level = (short) newLevel;
        predecessors = new ArrayList<Node>();
      }
      predecessors.add(predecessor);
      indegree -= 1;
      // if (indegree < 0) System.out.println(loc);
      return indegree == 0;
    }

    @Override
    public String toString() {
      return loc + " " + indegree + ":" + level + " p(" + predecessors.size() + ")";
    }
  }
}
